package com.lc.hot100.lc238;

public class Main {

}

/*
 * 	[1,2,3,4]
 * 	[1,1,2,3,4,1]
 * 
 * 
 * 
 * 	
 */

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        
        int[] res = new int[n];
        
        int[] pre = new int[n + 2];
        int[] suf = new int[n + 2];
        int[] t = new int[n + 2];
        for (int i = 1; i <= n; i ++) {
        	t[i] = nums[i - 1];
        }
        
        pre[0] = 1;
        for (int i = 1; i <= n; i ++) {
        	pre[i] = pre[i - 1] * t[i];
        }
        suf[n + 1] = 1;
        for (int i = n; i > 0; i --) {
        	suf[i] = suf[i + 1] * t[i];
        }
        for (int i = 1; i <= n; i ++) {
        	res[i - 1] = pre[i - 1] * suf[i + 1];
        }
        
        return res;
    }
}
